package org.xqh.study.leetcode.algorithm;

/**
 * @ClassName FindKthAlgorithm
 * @Description 两个有序数组 寻找第k小的 数
 * @Author xuqianghui
 * @Date 2021/1/6 21:30
 * @Version 1.0
 */
public class FindKthAlgorithm {

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 4};
        int[] nums2 = {1, 5, 7, 9, 11, 12, 13, 15, 18 ,19};
        System.out.println(findKthNum2(nums1, nums2, 7));
    }

    /**
     * 寻找第k大的数组
     * @param nums1 有序数组1
     * @param nums2 有序数组2
     * @param k 第k小
     * @return
     */
    public static int findKthNum2(int[] nums1, int[] nums2, int k){
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int m = nums1.length;
        int left = 0;//数组1  分割线 左侧 指针
        int right = m;// 数组1 分割线 右侧 指针
        while (left < right){
            //二分法查找
            int i = left + (right - left + 1)/ 2;//数组1 位置
            int j = k - i;//数组2 位置
            if(nums1[i - 1] > nums2[j]){
                right = i - 1;
            }else {
                left = i;
            }
        }
        int i = left;
        int j = k - i;
        int oneLeftVal = nums1[i - 1];
        int twoLeftVal = nums2[j - 1];
        return Math.max(oneLeftVal, twoLeftVal);
    }

    @Deprecated
    public static int findKthNum(int[] nums1, int[] nums2, int k) {
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }

        int n1 = 0;//数组1 指针
        int n2 = 0;//数组2 指针
        while (n1 + n2 < k) {
            int idx = (k - n1 - n2 + 1) / 2;
            int i1 = (n1 + idx) > nums1.length ? (nums1.length - 1) : n1 + idx - 1;
            int plus = (n1 + idx) > nums1.length ? (nums1.length - n1) : idx;
            if(n1 == nums1.length){
                //第一个数组 已经 全部移除
                n2 = k - n1;
                break;
            }
            if (nums1[i1] < nums2[n2 + idx - 1]) {
                //数组1 < 数组2 对应位置 移除数组1
                n1 += plus;
            } else if (nums1[i1] > nums2[n2 + idx - 1]) {
                n2 += idx;
            } else {
                //相等的情况
                n1 += plus;
                n2 += idx;
            }
        }
        return Math.max(nums1[n1-1] , nums2[n2-1]);
    }
}
